A Galois field GF(n) is a set of elements that allows binary operations, such as addition and multiplication operations. Computations of Galois field elements are frequently seen in communication systems and encryption standards, such as encryption standards for wireless applications. For example, Wireless Local Area Networks (WLAN) may rely on the use of encryptions to ensure security of data transmitted wirelessly. One of the WLAN standard, IEEE 802.11i, incorporates Advanced Encryption Standard (AES) by the National Institute of Standards and Technology (NIST), and the AES is based on Rijndael Block Cipher. In implementing the AES, Galois field is used for various computations, which may consume a majority of hardware resources. In particular, computations of inversions in Galois field, such as GF(28), is one of the primary factors in consuming hardware resources.
Conventional implementation uses a look-up table to store the multiplicative inverses for all 255 nonzero elements in GF(28). This approach is straightforward and has little latency, but requires a lot of logic gates, hence, a larger area in ASIC and higher power consumption. A well-known approach is to use the Extended Euclidean Algorithm (EEA). For example, assuming the field GF(28) is constituted by some irreducible polynomial f(x) of degree eight. By the irreducibility of f(x), every nonzero element in GF(28), when represented in its polynomial form, such as p(x) is co-prime to f(x). That is, the greatest common divisor between f(x) and p(x) is one.
The EEA can then be used to find two polynomials q(x) and r(x) so that p(x) q(x)+f(x) r(x)=1. Conducing modulo-reduction on both sides by f(x), one may obtain p(x) q(x)=1 mod(f(x)), and hence, q(x) is exactly the multiplicative inverse of p(x) in GF(28). Generally, to find multiplicative inverse in GF(2m), the EEA requires 2m time steps and has an area complexity of O(m). This method requires less hardware, but may suffer from larger latency, which will not be suitable for a high-throughput system, such as a WLAN system.
An alternate approach includes performing the required computations in the sub-field to reduce hardware complexity. Observing that the field GF(24) is a sub-field of GF(28), GF(28) can be constructed by using some primitive polynomial g(x)=x2+x+λ for some λ in GF(24). In this approach, all computations are done in the sub-field GF(24). To compute inv(x), the above algorithm requires 4 multiplications and one multiplicative inversion in GF(16). Due to the complexity of the traditional techniques, there is a need for a technique for computing Galois field inversions that may bring simplicity in computation of hardware and software implementations.